package main

import (
	"fmt"
)

/*
背包容量4
物品重量[1,4,3]
物品价值[1500, 3000, 2000]
物品都只有一样，怎样取装下的总价值最大
*/

/*
注意问题：
dp数组的意义，dp[i][j]代表在<=j范围内，前i个物品（<=i）加入背包时，背包的最值（最值指的是符合题目条件的值）
dp数组有base case所以容量比数量多1
取值的时候，例如取物品的重量和价值的时候，需要-1才是物品在原数组中的index（因为有base case）
状态转移的时候，都是与当前假设状态j进行比较，不是与题目实际背包情况比较
*/
func cal(pkg int, things []int, thingVal []int) (maxVal int) {
	// 1 DP数组，行代表物品种类，列代表背包容量，创建(n+1)*(m+1)的数组
	var dp [][]int
	for i := 0; i < len(things)+1; i++ {
		dp = append(dp, make([]int, pkg+1))
	}
	// 1.1 额外内容，背包存放了哪些东西
	var contain [][][]int
	for i := 0; i < len(things)+1; i++ {
		contain = append(contain, make([][]int, pkg+1))
	}
	// 2 base case
	// 首行意义：没有物品可选，不管背包容量多大，存放的最大价值都是0；
	// 首列意义：背包容量为0，不管有什么物品可选，存放的最大价值都是0
	for i := 0; i < len(dp); i++ {
		for j := 0; j < len(dp[i]); j++ {
			if i == 0 {
				dp[i][j] = 0
				continue
			}
			if j == 0 {
				dp[i][j] = 0
				continue
			}
		}
	}
	// 3 遍历状态
	for i := 1; i < len(dp); i++ {
		for j := 1; j < len(dp[i]); j++ {
			// 4 选择，状态转移方程，穷举
			// 如果物品重量超过当前假设的背包容量dp[*][j]，这dp[i][j]最大价值只可能是dp[i-1][j]
			N := i - 1 // 注意index偏移，因为dp数组初始化的时候增加了0，0状态,所以物品i其实对应物品数组的序号是N=i-1
			if things[N] > j {
				dp[i][j] = dp[i-1][j]
				contain[i][j] = contain[i-1][j]
				continue
			}
			// 如果物品没有超出当前背包的假设容量，则尝试把当前物品加入，
			// 再比较不加入和加入情况下哪个符合要求，设置为当前dp[N][j]
			// 如果加入，则意味着肯定有这个物品，所以最大价值就是前i-1个物品在j-thing[N]容量下的最大值+当前物品的价值
			testAddMaxVal := dp[i-1][j-things[N]] + thingVal[N]
			// 如果不加入，则意味着这个物品不需要，最大值其实就是前i-1个物品在容量j情况下的最大值
			testNotAddmaxVal := dp[i-1][j]
			if testAddMaxVal > testNotAddmaxVal {
				// 背包内容包含contain[i-1][j-things[N]] 加入物品N，跟dp[i-1][j-things[N]] + thingVal[N]类似
				contain[i][j] = append(contain[i-1][j-things[N]], N)
				dp[i][j] = testAddMaxVal
			} else {
				contain[i][j] = contain[i-1][j]
				dp[i][j] = testNotAddmaxVal
			}
			// dp[i][j] = max(testAddMaxVal, testNotAddmaxVal)
		}
	}
	fmt.Println("val:")
	for i := 0; i < len(dp); i++ {
		fmt.Println(dp[i])
	}
	fmt.Println("things index:")
	for i := 0; i < len(contain); i++ {
		fmt.Println(contain[i])
	}
	maxVal = dp[len(things)][pkg]
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	pkg := 4
	things := []int{1, 4, 3}
	valThings := []int{1500, 3000, 2000}
	fmt.Println(cal(pkg, things, valThings))
}
